#!/usr/bin/env python
# -*- coding:utf-8 -*-

from gmpy2 import invert

def egcd(a,b):

	if a == 0:

		return b,0,1

	else:

		g,y,x = egcd(b%a,a)

		return g,x-(b//a)*y,y



def main():

	n = raw_input('Input n:')

	c1 = raw_input('Input c1:')

	c2 = raw_input('Input c2')

	e1 = raw_input('Input e1')

	e2 = raw_input('Input e2')

	'''

	n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211

	c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853

	c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
	
	e1 = 1804229351
	
	e2 = 17249876309

	'''

	s = egcd(e1,e2)

	s1 = s[1]

	s2 = s[2]

	if s1 < 0:

		s1 = -s1

		c1 = invert(c1,n)

	elif s2 <0:

		s2 = -s2

		c2 = invert(c2,n)

	m = pow(c1,s1,n)*pow(c2,s2,n) % n

	print m





if __name__ == '__main__':

	main()

'''

a = '666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573'

result = ''

for i in range(len(a)/2):

	result = result + chr(int(('0x'+a[i*2:(i+1)*2]),16))

print result

'''